O'Quinn came up the idea of publishing a one-time only magazine on the Star Trek phenomenon. Houston's editorial assistant Kirsten Russell suggested that they include an episode guide to all three seasons of the show, interviews with the cast and previously unpublished photographs. During this brainstorming session many questions were raised, most notably legal issues. Houston contacted Star Trek creator Gene Roddenberry with the intention of interviewing him for the magazine. Once they got his approval, O'Quinn and Jacobs proceeded to put together the magazine but Paramount Studios, who owned Star Trek, wanted a minimum royalty that was greater than their projected net receipts and the project was shelved. O'Quinn realized that they could create a magazine that only featured Star Trek content but without it being the focus and therefore getting around the royalties issue. He also realized that this could be the science fiction magazine he and Houston had talked about. Many titles for it were suggested, including Fantastic Films and Starflight before Starlog was chosen. (Fantastic Films was later used as the title of a competing science fiction magazine published by Blake Publishing.)

To keep costs down, Starlog was initially a quarterly magazine with the first issue being published on August 1976. The issue sold out and this encouraged O'Quinn and Jacobs to publish a magazine every six weeks instead of quarterly. O'Quinn was the magazine's first editor with Houston taking over for a year and then replaced by Howard Zimmerman when Houston was promoted to the "Hollywood Bureau." Zimmerman was eventually succeeded by David McDonnell.

One of the magazine's milestones was its 100th issue, published on November 1985 and featured who they thought were the 100 most important people in science fiction. This included exclusive interviews with John Carpenter, Peter Cushing, George Lucas, Leonard Nimoy, and Gene Roddenberry. The magazine's 200th issue repeated the format of the 100th issue but this time interviewed such notable artists as Arthur C. Clarke, Tim Burton, William Gibson, Gale Anne Hurd, and Terry Gilliam. Starlog was one of the first publications to report on the development of the first Star Wars movie, and it also followed the development of what was to eventually become Star Trek: The Motion Picture. The magazine was devoted to science fiction films, television series, and books. Many fans of this long-running magazine considered its heyday to have been the 1980s with very little substance to the content in later years and many of its long-time contributors having since moved on. But it continued to boast some top-flight genre journalists, including film historians Will Murray, Jean-Marc Lofficier and Tom Weaver. It was one of the longest-running and most popular publications of its type.

It published its 30th Anniversary issue in 2006. On Wednesday, December 5, 2007 at approximately 11 a.m. a warehouse, operated by Kable News, in Oregon, Illinois containing back issues of Starlog and Fangoria burned to the ground.